﻿

using System.ComponentModel.DataAnnotations;
using System.Linq;

namespace Graph.Algorithm.Core
{
    public class GeneticService
    {
        private int[] path { get; set; }
        public List<int> bestPath = new List<int>();

        private static Random randomBuilder = new Random();
        private static MatrixBuilder<double> matBuilder { get; set; } = Matrix<double>.Build;

        public int crossoverNum { get; set; }
        public int mutationNum { get; set; }
        public int populationNum { get; set; } = 500;
         
        private static Matrix<double> matrixDistance;

        public GeneticService(IEnumerable<GraphEdge> edges)
        {
            var groups = edges.GroupBy(e => e.stVertexId);
            var cityNum = groups.Count();
            matrixDistance = matBuilder.Dense(cityNum, cityNum);

            for (int i = 0; i < cityNum; i++)
            {
                for (int j = 0; j < cityNum; j++)
                {
                    matrixDistance[i, j] = i == j ? 0 : edges.At(i, j).weight;
                }
            }

            path = new int[cityNum];
            for (int i = 0; i < cityNum; i++)
            {
                path[i] = i;
            }
            bestPath = path.ToList();

            crossoverNum = cityNum / 2;
            mutationNum = cityNum / 10;
        }

        public GeneticService(Matrix<double> _matrixDistance)
        {
            matrixDistance = _matrixDistance;
            int cityNum = _matrixDistance.RowCount;

            path = new int[cityNum];
            for (int i = 0; i < cityNum; i++)
            {
                path[i] = i;
            }
            bestPath = path.ToList();

            crossoverNum = cityNum / 2;
            mutationNum = cityNum / 10;
        }

        public void RunAlgm(int numberOfGeneration)
        {
            List<int[]> population = new List<int[]>();
            for (int i = 0; i < populationNum; i++)
            {
                population.Add(path.OrderBy(p => randomBuilder.Next(path.Count())).ToArray());
            }

            while (numberOfGeneration > 0)
            {
                numberOfGeneration--;

                List<int[]> childs = new List<int[]>();
                for (int i = 0; i < crossoverNum; i++)
                {
                    var father = population[randomBuilder.Next(population.Count)];
                    var mother = population[randomBuilder.Next(population.Count)];
                    var child = Crossover(father, mother, father.Count() / 2);
                    if (child.Length != path.Length) continue;//染色体数量变化  定义为其他物种 不计入种群
                    childs.Add(child);
                }

                List<int[]> mutates = new List<int[]>();
                for (int i = 0; i < mutationNum; i++)
                {
                    var mutate = population[randomBuilder.Next(population.Count)];
                    mutate = Mutation(mutate);
                    if (mutate.Length != path.Length) continue;//染色体数量变化  定义为其他物种 不计入种群
                    mutates.Add(mutate);
                }

                population = population.Concat(childs).Concat(mutates)
                    .OrderBy(p => PathLength(p))
                    .ToList();

                population = population.GetRange(0, populationNum);

                //bool hasSame =   population.Any(p => p.GroupBy(v => v).Any(g => g.Count() > 1));
                // p.GroupBy(v => v).Any(g => g.Count() > 1)

            }

            bestPath = population.First().ToList();
        }


        /// <summary>
        /// 计算当前路径的总路程
        /// </summary>
        /// <param name="_paths"></param>
        /// <returns></returns>
        public static double PathLength(int[] _paths)
        {
            double pathSum = 0;
            for (int i = 0; i < _paths.Length - 1; i++)
            {
                pathSum += matrixDistance[_paths[i], _paths[i + 1]];
            }
            pathSum += matrixDistance[_paths.Last(), _paths.First()];
            return pathSum;
        }

        /// <summary>
        /// 染色体互换
        /// </summary>
        /// <param name="_pathSt"></param>
        /// <param name="_pathEd"></param>
        /// <param name="_num"></param>
        /// <returns></returns>
        public static int[] Crossover(int[] _pathSt, int[] _pathEd, int _num)
        {
            List<int> pathSt = _pathSt.ToList();
            List<int> pathEd = _pathEd.ToList();

            List<int> childChromosome = new List<int>();

            int num = _num;

            List<int> removeIndexs = new List<int>();
            for (int i = 0; i < num; i++)
            {
                removeIndexs.Add(randomBuilder.Next(pathEd.Count - 1));
            }

            List<int> removeValues = new List<int>();
            removeIndexs.ForEach(i => removeValues.Add(pathEd[i]));
            removeValues.ForEach(v => pathEd.Remove(v));
            var stSegment = pathSt.Where(p => removeValues.Contains(p)).ToList();

            childChromosome = pathEd.Concat(stSegment).ToList();

            return childChromosome.ToArray();
        }


        /// <summary>
        /// 随机长度编译
        /// </summary>
        /// <param name="_path"></param>
        /// <returns></returns>
        public static int[] Mutation(int[] _path)
        {
            var sourceChromosome = _path.ToList();
            var targetChromosome = _path.ToList();

            int index1 = randomBuilder.Next(sourceChromosome.Count);
            int index2 = randomBuilder.Next(sourceChromosome.Count);

            var minIndex = Math.Min(index1, index2);
            var maxIndex = Math.Max(index1, index2);
            if (minIndex == maxIndex) return sourceChromosome.ToArray();

            var mutationSt = sourceChromosome.GetRange(0, minIndex);
            var mutationSegment = sourceChromosome.GetRange(minIndex, maxIndex - minIndex);
            var mutationEd = sourceChromosome.GetRange(maxIndex, sourceChromosome.Count() - maxIndex);
            
            mutationSegment = mutationSegment.OrderBy(s => randomBuilder.Next()).ToList();

            targetChromosome = mutationSt.Concat(mutationSegment).Concat(mutationEd).ToList();
            //var EEE=    targetChromosome.GroupBy(v => v).Where(g => g.Count() > 1).Select(g=>g.First()).ToList();
            return targetChromosome.ToArray();
        }

        /// <summary>
        /// 指定编译片段长度
        /// </summary>
        /// <param name="_path"></param>
        /// <param name="_num"></param>
        /// <returns></returns>
        public static int[] Mutation(int[] _path, int _num)
        {
            var sourceChromosome = _path.ToList();
            int num = _num;

            var targetChromosome = _path.ToList();
            //防止完全超变异发生
            if (num > sourceChromosome.Count())
            {
                num = Int32.Parse((num / 2).ToString());
            }

            var minIndex = randomBuilder.Next(sourceChromosome.Count - num - 1);
            var maxIndex = minIndex + num;

            var mutationSt = sourceChromosome.GetRange(0, minIndex);
            var mutationSegment = sourceChromosome.GetRange(minIndex, maxIndex - minIndex);
            var mutationEd = sourceChromosome.GetRange(maxIndex, sourceChromosome.Count() - maxIndex);

            mutationSegment = mutationSegment.OrderBy(s => randomBuilder.Next()).ToList();

            targetChromosome = mutationSt.Concat(mutationSegment).Concat(mutationEd).ToList();

            return targetChromosome.ToArray();

        }

    }
}
